HW#2 --- last modified February 07 2019 04:29:34..

Solution set.

Due date: Mar 3

Files to be submitted:
  Hw2.zip

Purpose: To practice solving recurrence relations, to get a feeling for asymptotic notation, and try our hands at coding a heap.

The main course outcomes covered by this assignment are:

LO1 -- Implement lists, stacks, queues, search trees, heaps, union-find ADT, and graphs and use these data structures in programs they design.

LO4 -- Use advanced sorting techniques (radix sort, heapsort, mergesort, quicksort).

LO6 -- Solve recurrence relations representing the running time of an algorithm designed using a divide-and-conquer strategy.

Specification:

For this homework there will be two parts: a written part and a coding part. Remember, as I said on the syllabus, emailed homeworks will not be accepted. You must submit through the online submission to have your homework graded. It has a maximum upload file size of 2MB. Both parts of the homework should be submitted in your Hw2.zip file. For the written part I want you to do the following problems below, and put your solutions into a file Hw2.pdf (no Word docs please!) which you put in your zip file. Put your name and ID clearly on the front page of this file.

1. For each pair of expressions `(A,B)` in the table below indicate whether, `A` is `O`, `o`, `Omega`, `omega`, `Theta` of `B`. Your answer should be in the form of a table with "yes" or "no" written in each box. Pick one row from your table and show carefully your work to prove at least two statements from that row.

   A	B	O	o	`Omega`	`omega`	`Theta`
   `n^2`	`n^3`
   `log^star (log n)`	`log (log^\star n)`
   `log (n!)`	`n log n`
   `2^n`	`3^n`
   `n^(cos n)`	`n`

2. Solve the recurrence `T(n) = 3 T(n^(1/3)) + 1` using the substitution method.
3. Solve the recurrence `T(n) = T(n/4) + T((3n)/4) + O(n)` using the recursion tree method.
4. Use the master method to give an asymptotic tight bound for `T(n) = 4T(n/4) + n^4`.

`d`-ary heaps are define in the book on page 6.2. For the coding part of the homework, I would like you to modify the heapsort algorithm in the book so that it uses a 3-ary heap rather than the usual binary heap. You will code this algorithm in a file Hw2.java which should conform to the Departmental coding guidelines for Java. Include this file (but no class files or jars) in the Hw2.zip file you submit. It will be compiled from the command-line with the command:

javac Hw2.java

Your program will be tested from the command line by passing the sequence as command line arguments:

java Hw2 elt_1 elt_2 elt_3 ...

For example,

java Hw2 10 52 21 68 12 27

The output of your code should present the heap after the build heap phase (using your 3-ary build heap code), followed on the next line by the result from sorting. For the particular line above, you would get:

After Build Heap: 68 52 21 10 12 27
Final Sorted: 10 12 21 27 52 68

Your program should match the spacing above. If you would like to compare what your code does versus what I think it should output, you can use my compiled Python version of 3-ary heapsort.

Point Breakdown